package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 找到字符串中所有字母异位词 {
    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";


        System.out.println(findAnagrams(s, p));
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int left = 0, right = 0;
        if (s.length() < p.length()) return null;
        char[] charS = s.toCharArray();
        char[] charP = p.toCharArray();
        int[] sInt = new int[26];
        int[] pInt = new int[26];
        for (int i = 0; i < p.length(); i++) {
            // [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
            pInt[charP[i] - 'a']++;
        }
        while (right < s.length()) {
            // 依次计算出s每个数值与a的差异值。当作数组sInt的下标。sInt中该下标上的值：表示这个数值在s中出现的次数
            int rightVal = charS[right] - 'a';
            // 当这个取值不存在，使用1表示；当数值存在时，++表示出现的次数
            sInt[rightVal]++;
            if ((right - left) + 1 > p.length()) {
                sInt[charS[left++] - 'a']--;
            }
            if ((right - left) + 1 == p.length()) {
                if (Arrays.equals(sInt, pInt)) {
                    res.add(left);
                }
            }
            right++;
        }
        return res;
    }


}
